import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/17 8:36
 * @description 字典树 数据结构
 */
public class Trie {
    /**
     * 指向子节点的指针数组
     */
    public Trie[] children;
    /**
     * 该节点是否为字符串的结尾
     */
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    /**
     * 插入word字符串到字典树中
     * @param word word字符串
     */
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                // 不存在赋值
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        // 最后的一个节点结尾了，那么要设置为true
        node.isEnd = true;
    }

    /**
     * 查找是否有前缀单词，
     * @param prefix 前缀
     * @return 字典树
     */
    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }

    /**
     * 查找字符串是否存在
     * @param word word
     * @return true or false
     */
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        // 存在的定义为该树节点存在且该节点结尾了
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        // 是否已前缀开始，只要返回的节点不为null即可
        return searchPrefix(prefix) != null;
    }
}
